#include <iostream>
#include "SortTestHelper.h"
#include "MergeSort.h"
using namespace std;

template<typename T>
int __partition(T arr[],int l,int r){
    swap(arr[l],arr[rand()%(r-l+1)+l]);
    T v=arr[l];
    int  j=l;
    for (int i = l+1; i <=r;i++)
        if (arr[i]<v) {
            j++;
            swap(arr[j],arr[i]);
        }

    swap(arr[l],arr[j]);
    return j;
}
template<typename T>
int __partition2(T arr[],int l,int r){
    swap(arr[l],arr[rand()%(r-l+1)+l]);
    T v=arr[l];
    int i=l+1,j=r;
    while(true){
        while(i<=r&&arr[i]<v) i++;
        while(j>=l+1&&arr[j]>v) j--;
        if(i>j)
            break;
        swap(arr[i],arr[j]);
        i++;
        j--;
    }
    swap(arr[l],arr[j]);
        return j;
}
template<typename T>
void __quickSort2(T arr[], int l, int r) {
//        if (l>=r)
//            return;
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
    int p = __partition2(arr, l, r);
    __quickSort2(arr, l, p - 1);
    __quickSort2(arr, p+1, r);
}
template<typename T>
void __quickSort(T arr[], int l, int r) {
//        if (l>=r)
//            return;
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
    int p = __partition(arr, l, r);
    __quickSort(arr, l, p - 1);
    __quickSort(arr, p+1, r);
}
template <typename T>
void __quickSort3Ways(T arr[],int l,int r){
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
    swap(arr[l],arr[rand()%(r-l+1)+l]);
    T v=arr[l];
    int lt=l,i=l+1,gt=r+1;
    while (i<gt) {
        if(arr[i]<v) {
            lt++;
            swap(arr[i],arr[lt]);
            i++;
        } else if (arr[i]> v) {
            gt--;
            swap(arr[i], arr[gt]);
        } else {
            i++;
        }
    }
    swap(arr[l],arr[lt]);
    __quickSort3Ways(arr,l,lt-1);
    __quickSort3Ways(arr,gt,r);
}
template<typename T>
void quickSort3Ways(T arr[], int n) {
    srand(time(NULL));
    __quickSort3Ways(arr,0,n-1);
}
template<typename T>
void quickSort(T arr[], int n) {
    srand(time(NULL));
    __quickSort(arr,0,n-1);
}
template<typename T>
void quickSort2(T arr[], int n) {
    srand(time(NULL));
    __quickSort2(arr,0,n-1);
}
int main() {
       int n=100000;
        int* arr1=SortTestHelper::generateRandomArray(n,0,n);
        int* arr2=SortTestHelper::copyIntArray(arr1,n);
        int* arr3=SortTestHelper::copyIntArray(arr1,n);
        int* arr4=SortTestHelper::copyIntArray(arr1,n);
        SortTestHelper::testSort("merge sort",mergeSort,arr1,n);
        SortTestHelper::testSort("quick sort",quickSort,arr2,n);
        SortTestHelper::testSort("quick sort 2",quickSort2,arr3,n);
        SortTestHelper::testSort("quick sort 3",quickSort3Ways,arr4,n);


        delete[] arr1;
        delete[] arr2;
        delete[] arr3;
        delete[] arr4;

        int swapTimes = 100;
        cout<<"Test for nearly ordered array, size = "<<n<<", swap time = "<<swapTimes<<endl;
        arr1 = SortTestHelper::generateNearlyOrderedArray(n,swapTimes);
        arr2 = SortTestHelper::copyIntArray(arr1, n);
        arr3=SortTestHelper::copyIntArray(arr1,n);
        arr4=SortTestHelper::copyIntArray(arr1,n);
        SortTestHelper::testSort("merge sort",mergeSort,arr1,n);
        SortTestHelper::testSort("quick sort",quickSort,arr2,n);
        SortTestHelper::testSort("quick sort 2",quickSort2,arr3,n);
        SortTestHelper::testSort("quick sort 3",quickSort3Ways,arr4,n);

        delete[] arr1;
        delete[] arr2;
        delete[] arr3;
        delete[] arr4;
        return 0;
    }